use crate::cmp::Cmp;
use crate::types::SequenceNumber;

use std::cmp::Ordering;
use std::io::Write;

use integer_encoding::{FixedInt, FixedIntWriter, VarInt, VarIntWriter};

// The following typedefs are used to distinguish between the different key formats used internally
// by different modules.

// TODO: At some point, convert those into actual types with conversions between them. That's a lot
// of boilerplate, but increases type safety.

/// 这个 ValueType 枚举用于标识键值对（Key-Value）的操作类型，常见于存储引擎或数据库系统中，用于区分对数据的不同操作意图。
#[derive(Debug, Clone, Copy, PartialOrd, PartialEq)]
pub enum ValueType {
    /// 表示这是一个 "删除操作" 的标识。当需要从存储中删除某个键（Key）时，会使用该类型标记，表明对应的键应该被移除。
    TypeDeletion = 0,
    /// 表示这是一个 "插入或更新操作" 的标识。当需要向存储中插入新的键值对，或者更新已有键的值时，会使用该类型标记，表明需要存储或更新对应的键值对数据。
    TypeValue = 1,
}

/// A MemtableKey consists of the following elements: [keylen, key, tag, (vallen, value)] where
/// keylen is a varint32 encoding the length of key+tag. tag is a fixed 8 bytes segment encoding
/// the entry type and the sequence number. vallen and value are optional components at the end.
///
/// 表示内存表（MemTable）中使用的键类型，是一个字节切片引用
///
/// 结构明确规定为：[keylen, key, tag, (vallen, value)]
///
/// keylen：varint32 编码，记录 key+tag 的总长度
///
/// key：实际的键数据
///
/// tag：固定 8 字节，包含条目类型（如插入 / 删除）和序列号（用于版本控制）
///
/// vallen 和 value：可选部分，存储值的长度和值数据
pub type MemtableKey<'a> = &'a [u8];

/// A UserKey is the actual key supplied by the calling application, without any internal
/// decorations.
///
/// 表示应用程序提供的原始键，不包含任何系统内部添加的元数据
///
/// 是最纯粹的用户输入键，不带有存储引擎内部使用的标记或版本信息
pub type UserKey<'a> = &'a [u8];

/// An InternalKey consists of [key, tag], so it's basically a MemtableKey without the initial
/// length specification. This type is used as item type of MemtableIterator, and as the key
/// type of tables.
///
/// 表示存储引擎内部使用的键，结构为 [key, tag]
///
/// 可以看作是 MemtableKey 去掉开头长度标识的部分
///
/// 主要用于内存表迭代器（MemtableIterator）的条目类型和底层表（如 SSTable）的键类型
pub type InternalKey<'a> = &'a [u8];

/// A LookupKey is the first part of a memtable key, consisting of [keylen: varint32, key: *u8,
/// tag: u64]
/// keylen is the length of key plus 8 (for the tag; this for LevelDB compatibility)
///
/// LookupKey 结构体是数据库在查询操作中用于解析和处理 “内部键” 的工具，主要作用是将用户传入的原始键（UserKey）与查询相关的元数据（如序列号）组合成符合内存表 / SSTable 格式的 “内部键”，
/// 同时提供便捷的解析能力，帮助快速提取键的核心信息（用户键、序列号等）。
#[derive(Clone, Debug)]
pub struct LookupKey {
    /// 存储完整的 “内部键” 或 “查询用键前缀”（字节流），符合 build_memtable_key 定义的格式。
    key: Vec<u8>,
    /// 标记 key 字节流中 “用户原始键（UserKey）” 的起始偏移量（便于快速提取用户键）。
    key_offset: usize,
}

const U64_SPACE: usize = 8;

impl LookupKey {
    /// 这个 new 是为了组成新的查询条件, 不单单是一个 key, seq, 而是一个 key, seq, TypeValue 组成的新的查询方式
    pub fn new(k: UserKey, s: SequenceNumber) -> LookupKey {
        LookupKey::new_full(k, s, ValueType::TypeValue)
    }
    /// 这个 new_full 方法是 LookupKey 结构体的构造函数，用于创建一个包含完整信息的 LookupKey 实例。
    /// LookupKey 是 LSM 树存储引擎中用于封装 “用户键 + 序列号 + 操作类型” 的关键结构，主要用于键的查找、比较和内部键的生成。
    ///
    ///方法接收三个参数：k: UserKey（用户键）、s: SequenceNumber（序列号）、t: ValueType（操作类型，如插入或删除），返回 LookupKey 实例，
    ///
    /// 核心作用
    ///
    /// new_full 方法的核心价值是标准化内部键的生成过程，主要作用包括：
    ///
    /// 1.封装内部键结构
    ///
    /// LSM 树的内部键需要包含用户键、序列号（用于版本控制）和操作类型（用于标记插入 / 删除），new_full 按固定格式将这些信息打包，确保内部键的一致性。
    ///
    /// 2.支撑键的比较与查找
    ///
    /// 生成的 LookupKey 可用于 SSTable 中的键查找、迭代器比较等场景，例如：
    ///
    /// 通过 internal_key() 方法提取完整内部键，用于与 SSTable 中的键比较；
    ///
    /// 通过 user_key() 方法快速提取用户键，用于上层逻辑处理。
    ///
    /// 3.优化内存使用
    ///
    /// 提前计算并分配缓冲区大小，避免动态扩容；使用变长编码存储长度，减少不必要的空间占用。
    ///
    /// 与 LookupKey::new 的区别
    ///
    /// 通常 LookupKey 还有一个简化的 new 方法（如 LookupKey::new(k, s)），仅接收用户键和序列号，默认操作类型为插入。而 new_full 允许显式指定操作类型，更灵活地支持删除等场景。
    pub fn new_full(k: UserKey, s: SequenceNumber, t: ValueType) -> LookupKey {
        // U64_SPACE 通常是 8（表示 64 位整数占用的字节数），因为序列号（SequenceNumber）和操作类型（ValueType）会打包成一个 64 位整数存储；
        // internal_keylen.required_space() 计算内部键长度的 “变长编码” 所需空间（LSM 树中常用变长编码存储长度，节省空间）；
        // key.resize(...) 提前分配足够的缓冲区，避免后续动态扩容的性能开销。
        let mut key = Vec::new();
        // 计算内部键（用户键 + 序列号 + 操作类型）的长度
        let internal_keylen = k.len() + U64_SPACE;  // U64_SPACE 是 8 字节（序列号+类型占 8 字节）
        // 预留足够空间：用户键长度 + 内部键变长编码所需空间 + 8 字节（序列号+类型）
        key.resize(k.len() + internal_keylen.required_space() + U64_SPACE, 0);

        {
            // 变长编码长度：write_varint(internal_keylen) 用变长编码存储内部键的总长度（用户键长度 + 8 字节），相比固定 4 字节 / 8 字节更节省空间；
            // 用户键：write_all(k) 将原始用户键（如 b"user_key_123"）写入缓冲区；
            // 序列号 + 操作类型：(s << 8) | t as u64 将 64 位序列号左移 8 位，低 8 位存储操作类型（如 ValueType::TypeValue 表示插入，TypeDeletion 表示删除），再通过 write_fixedint 写入 8 字节固定长度数据。
            let mut writer = key.as_mut_slice(); // 将缓冲区作为可写切片
            // 写入内部键长度的变长编码
            writer.write_varint(internal_keylen).expect("write to slice failed");
            // 写入用户键原始数据
            writer.write_all(k).expect("write to slice failed");
            // 写入打包后的序列号和操作类型（高 56 位是序列号，低 8 位是操作类型）
            writer.write_fixedint((s << 8) | t as u64).expect("write to slice failed");
        }
        // key 存储完整的编码数据，包含所有信息；
        // key_offset 记录用户键在缓冲区中的起始位置（跳过变长编码的长度部分），方便后续快速提取用户键。
        LookupKey {
            key,  // 完整的键缓冲区（变长长度 + 用户键 + 序列号+类型）
            key_offset: internal_keylen.required_space(),  // 用户键在缓冲区中的起始偏移量
        }
    }

    /// Returns the full memtable-formatted key.
    ///
    /// 这段代码定义了一个名为 memtable_key 的方法，用于返回内存表（MemTable）格式的完整键（MemtableKey）。
    ///
    /// 方法返回类型是 MemtableKey，即之前定义的内存表专用键类型（包含键长度、实际键、标签、值长度和值等信息的字节切片）
    ///
    /// 实现逻辑是 self.key.as_slice()，将当前结构体中存储的 key 字段转换为字节切片并返回
    pub fn memtable_key(&self) -> MemtableKey {
        self.key.as_slice()
    }

    /// Returns only the user key portion.
    ///
    /// 这段代码定义了一个名为 user_key 的方法，用于从内部存储的键数据中提取出纯粹的用户键（UserKey）部分。
    ///
    /// 核心逻辑是通过切片操作 &self.key[self.key_offset..self.key.len() - 8] 提取用户键：
    ///
    /// self.key 是包含完整内部键数据的字节容器
    ///
    /// self.key_offset 表示用户键在完整键中的起始偏移位置（跳过前面的长度等元数据）
    ///
    /// self.key.len() - 8 表示用户键的结束位置（减去末尾 8 字节的标签数据，标签通常包含条目类型和序列号等内部信息）
    pub fn user_key(&self) -> UserKey {
        &self.key[self.key_offset..self.key.len() - 8]
    }

    /// Returns key and tag.
    ///
    /// 这段代码定义了一个名为 internal_key 的方法，用于从存储的键数据中提取出内部键（InternalKey）。
    ///
    /// 方法返回类型是 InternalKey，即之前定义的存储引擎内部使用的键类型（结构为 [key, tag]，包含实际键数据和 8 字节标签）
    ///
    /// self.key 是包含完整键数据的字节容器
    ///
    /// self.key_offset 表示内部键在完整键中的起始偏移位置（跳过前面的长度等元数据）
    ///
    /// 切片从 key_offset 开始到末尾，包含了原始键数据和后续的 8 字节标签（符合 InternalKey 的结构定义）
    pub fn internal_key(&self) -> InternalKey {
        &self.key[self.key_offset..]
    }
}

/// Parses a tag into (type, sequence number)
///
/// 这个 parse_tag 函数用于用于解析内部键（InternalKey）中的 8 字节标记（tag），将其拆分为操作类型（ValueType）和序列号（SequenceNumber），是处理数据库内部键元数据的基础工具。
///
/// 核心背景：标记（tag）的结构
///
/// 在 LSM 树存储引擎中，内部键的末尾会附加一个 8 字节（64 位）的标记，用于存储键的元数据：
///
/// 低 8 位：表示操作类型（ValueType），如 “正常数据” 或 “删除标记”；
///
/// 高 56 位：表示序列号（SequenceNumber），用于版本控制（序列号越大，数据越新）。
///
/// 这种紧凑的存储方式既节省空间，又能快速解析关键元数据。
pub fn parse_tag(tag: u64) -> (ValueType, u64) {
    // 通过右移 8 位，丢弃低 8 位的操作类型，保留高 56 位作为序列号（seq）。
    let seq = tag >> 8;
    // 通过与 0xff（二进制 11111111）按位与，仅保留低 8 位，得到操作类型的原始数值（typ）。
    let typ = tag & 0xff;
    match typ {
        0 => (ValueType::TypeDeletion, seq),
        1 => (ValueType::TypeValue, seq),
        _ => (ValueType::TypeValue, seq),
    }
}

/// A memtable key is a bytestring containing (keylen, key, tag, vallen, val). This function
/// builds such a key. It's called key because the underlying Map implementation will only be
/// concerned with keys; the value field is not used (instead, the value is encoded in the key,
/// and for lookups we just search for the next bigger entry).
/// keylen is the length of key + 8 (to account for the tag)
///
/// 这个 build_memtable_key 函数是 LSM 树存储引擎中内存表（MemTable）的核心编码工具，
///
/// 用于将用户传入的键、值、操作类型和序列号，按照固定格式组装成内存表内部使用的 “统一键（Memtable Key）”。
///
/// 它的本质是将键值对的完整元数据编码到一个字节流中，供内存表的底层数据结构（如跳表）进行排序和存储。
pub fn build_memtable_key(key: &[u8], value: &[u8], t: ValueType, seq: SequenceNumber) -> Vec<u8> {
    // We are using the original LevelDB approach here -- encoding key and value into the key that is used for insertion into the SkipMap.
    // The format is: [key_size: varint32, key_data: [u8], flags: u64, value_size: varint32, value_data: [u8]]

    // U64_SPACE 8 字节对应 flags
    // flags 组合逻辑：(t as u64) | (seq << 8)
    // 例如：操作类型为 TypeValue（假设值为 1）、序列号为 100，flags 为 1 | (100 << 8) = 0x6401（64 是 100 的十六进制，左移 8 位后占高字节，1 占低字节）。
    let keysize = key.len() + U64_SPACE;
    let valsize = value.len();
    let mut buf = vec![0_u8; keysize + valsize + keysize.required_space() + valsize.required_space()];

    {
        let mut writer = buf.as_mut_slice();
        writer.write_varint(keysize).expect("write to slice failed"); // 写入 key_data+flags 的总长度
        writer.write_all(key).expect("write to slice failed"); // 写入原始键；
        writer.write_fixedint((t as u64) | (seq << 8)).expect("write to slice failed"); // 写入操作类型 + 序列号的组合标记；
        writer.write_varint(valsize).expect("write to slice failed"); // 写入原始值的长度；
        writer.write_all(value).expect("write to slice failed"); // 写入原始值。
        assert_eq!(writer.len(), 0);
    }
    buf
}

/// Parses a memtable key and returns  (keylen, key offset, tag, vallen, val offset).
/// If the key only contains (keylen, key, tag), the vallen and val offset return values will be
/// meaningless.
///
/// 这个 parse_memtable_key 函数是 build_memtable_key 函数的 “反向操作”，用于解析内存表中存储的 “统一键（Memtable Key）”，
///
/// 从中提取出原始键、值、操作类型和序列号等核心信息。它是内存表查询流程中解析数据的关键工具。
///
/// mkey: MemtableKey，即 build_memtable_key 生成的字节流
pub fn parse_memtable_key(mkey: MemtableKey) -> (usize, usize, u64, usize, usize) {
    // 解析 keylen（键 + 标记的总长度）
    let (keylen, mut i): (usize, usize) = VarInt::decode_var(mkey).unwrap();
    let keyoff = i; // 原始键的起始偏移量
    i += keylen - 8; // 跳过原始键（`keylen-8` 是原始键的实际长度，8字节是后续的标记）, 意思是偏移量 i 移动到 “标记（tag）” 字段的起始位置。

    if mkey.len() > i {
        // tag 是一个 64 位整数，低 8 位是操作类型（ValueType），高 56 位是序列号（SequenceNumber），与 build_memtable_key 中的编码逻辑对应。
        let tag = FixedInt::decode_fixed(&mkey[i..i + 8]); // 读取8字节固定长度的标记
        i += 8; // 偏移量跳过标记字段
        let (vallen, j): (usize, usize) = VarInt::decode_var(&mkey[i..]).unwrap(); // 读取值的长度, vallen 是原始值（value）的长度
        i += j; // 偏移量跳过 `vallen` 占用的字节
        let valoff = i; // 值的起始偏移量, valoff 记录原始值在 mkey 中的起始位置
        (keylen - 8, keyoff, tag, vallen, valoff)
    } else {
        (keylen - 8, keyoff, 0, 0, 0)
    }
}

/// cmp_memtable_key efficiently compares two memtable keys by only parsing what's actually needed.
pub fn cmp_memtable_key(ucmp: &dyn Cmp, a: MemtableKey<'_>, b: MemtableKey<'_>) -> Ordering {
    let (alen, aoff): (usize, usize) = VarInt::decode_var(a).unwrap();
    let (blen, boff): (usize, usize) = VarInt::decode_var(b).unwrap();
    let userkey_a = &a[aoff..aoff + alen - 8];
    let userkey_b = &b[boff..boff + blen - 8];

    match ucmp.cmp(userkey_a, userkey_b) {
        Ordering::Less => Ordering::Less,
        Ordering::Greater => Ordering::Greater,
        Ordering::Equal => {
            let atag = FixedInt::decode_fixed(&a[aoff + alen - 8..aoff + alen]);
            let btag = FixedInt::decode_fixed(&b[boff + blen - 8..boff + blen]);
            let (_, aseq) = parse_tag(atag);
            let (_, bseq) = parse_tag(btag);

            // reverse!
            bseq.cmp(&aseq)
        }
    }
}

/// Parse a key in InternalKey format.
///
/// 这个 parse_internal_key 函数用于解析数据库中的 “内部键（InternalKey）”，从中提取出关键信息：操作类型、序列号和用户原始键。
///
/// 它是处理内部键的基础工具函数，在查询、压缩等多个流程中都会用到。
pub fn parse_internal_key(ikey: InternalKey) -> (ValueType, SequenceNumber, UserKey) {
    if ikey.is_empty() {
        return (ValueType::TypeDeletion, 0, &ikey[0..0]);
    }
    // 断言内部键长度至少为 8 字节（因为标记部分固定为 8 字节），确保后续解析安全。
    assert!(ikey.len() >= 8);
    // 提取内部键的最后 8 字节（标记部分），通过 FixedInt::decode_fixed 转换为 64 位整数；
    // 调用 parse_tag 函数（通常是将 64 位整数拆分：低 8 位为 ValueType，高 56 位为 SequenceNumber），得到操作类型和序列号。
    let (typ, seq) = parse_tag(FixedInt::decode_fixed(&ikey[ikey.len() - 8..]));
    (typ, seq, &ikey[0..ikey.len() - 8])
}

/// cmp_internal_key efficiently compares keys in InternalKey format by only parsing the parts that
/// are actually needed for a comparison.
pub fn cmp_internal_key(ucmp: &dyn Cmp, a: InternalKey<'_>, b: InternalKey<'_>) -> Ordering {
    match ucmp.cmp(&a[0..a.len() - 8], &b[0..b.len() - 8]) {
        Ordering::Less => Ordering::Less,
        Ordering::Greater => Ordering::Greater,
        Ordering::Equal => {
            let seqa = parse_tag(FixedInt::decode_fixed(&a[a.len() - 8..])).1;
            let seqb = parse_tag(FixedInt::decode_fixed(&b[b.len() - 8..])).1;
            // reverse comparison!
            seqb.cmp(&seqa)
        }
    }
}

/// truncate_to_userkey performs an in-place conversion from InternalKey to UserKey format.
///
/// 这个 truncate_to_userkey 函数是 LSM 树存储引擎中用于处理内部键（InternalKey）和用户键（UserKey）转换的工具函数，
///
/// 作用是从数据库内部存储的键（包含额外元数据）中剥离附加信息，提取出用户原始输入的键。
pub fn truncate_to_userkey(ikey: &mut Vec<u8>) {
    let len = ikey.len();
    // 数据库内部存储的键（InternalKey）由两部分组成：用户键（UserKey） + 8 字节元数据；
    // 8 字节元数据通常包含：序列号（SequenceNumber，64 位或 56 位）和操作类型（如插入、删除，8 位）；
    // assert! 确保输入的是合法的内部键（避免处理无效数据导致逻辑错误）。
    assert!(len >= 8);  // 确保内部键长度至少为 8 字节（元数据部分的固定长度）
    // truncate(n) 是 Rust 中 Vec 的方法，用于将向量长度截断为 n，保留前 n 个字节，丢弃后续内容；
    // 这里通过 len - 8 计算用户键的长度，截断后向量中仅保留原始的用户键字节。
    ikey.truncate(len - 8);// 从长度中减去 8 字节，移除元数据部分
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_memtable_lookupkey() {
        use integer_encoding::VarInt;

        let lk1 = LookupKey::new("abcde".as_bytes(), 123);
        let lk2 = LookupKey::new("xyabxy".as_bytes(), 97);

        // Assert correct allocation strategy
        assert_eq!(lk1.key.len(), 14);
        assert_eq!(lk1.key.capacity(), 14);

        assert_eq!(lk1.user_key(), "abcde".as_bytes());
        assert_eq!(u32::decode_var(lk1.memtable_key()).unwrap(), (13, 1));
        assert_eq!(
            lk2.internal_key(),
            vec![120, 121, 97, 98, 120, 121, 1, 97, 0, 0, 0, 0, 0, 0].as_slice()
        );
    }

    #[test]
    fn test_build_memtable_key() {
        assert_eq!(
            build_memtable_key(
                "abc".as_bytes(),
                "123".as_bytes(),
                ValueType::TypeValue,
                231
            ),
            vec![11, 97, 98, 99, 1, 231, 0, 0, 0, 0, 0, 0, 3, 49, 50, 51]
        );
        assert_eq!(
            build_memtable_key("".as_bytes(), "123".as_bytes(), ValueType::TypeValue, 231),
            vec![8, 1, 231, 0, 0, 0, 0, 0, 0, 3, 49, 50, 51]
        );
        assert_eq!(
            build_memtable_key(
                "abc".as_bytes(),
                "123".as_bytes(),
                ValueType::TypeDeletion,
                231
            ),
            vec![11, 97, 98, 99, 0, 231, 0, 0, 0, 0, 0, 0, 3, 49, 50, 51]
        );
        assert_eq!(
            build_memtable_key(
                "abc".as_bytes(),
                "".as_bytes(),
                ValueType::TypeDeletion,
                231
            ),
            vec![11, 97, 98, 99, 0, 231, 0, 0, 0, 0, 0, 0, 0]
        );
    }

    #[test]
    fn test_build_parse(){
        let vec = build_memtable_key("abc".as_bytes(), "123".as_bytes(), ValueType::TypeValue, 231);
        println!("{:?}", vec);
        let key = parse_memtable_key(&vec);
        println!("{:?}", key);
    }
}
